Online social networks allow users to interact by posting messages to individual and common message feeds. Additionally, a first user may search for and discover other users using search terms that correspond to an interest of the first user. The first user may then subscribe to a second user's social network message feed, for example, by requesting to be added to a social graph associated with the second user, or by subscribing to a public message feed that does not require permission. A notification may then be provided to the second user (for example, within the message feed) to alert the second user of the subscription or request.